package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/merge-nodes-in-between-zeros'>合并零之间的节点(Merge Nodes in Between Zeros)</a>
 * <p>给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。</p>
 * <p>对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。</p>
 * <p> 返回修改后链表的头节点 head 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [0,<a color='green'>3</a>,<a color='green'>1</a>,0,<a color='red'>4</a>,<a color='red'>5</a>,<a color='red'>2</a>,0]
 *      输出：[4,11]
 *      解释：
 *          上图表示输入的链表。修改后的链表包含：
 *          - 标记为绿色的节点之和：3 + 1 = 4
 *          - 标记为红色的节点之和：4 + 5 + 2 = 11
 *
 * 示例 2：
 *      输入：head = [0,<a color='green'>1</a>,,0,<a color='red'>3</a>,0,<a color='blue'>2</a>,<a color='blue'>2</a>,0]
 *      输出：[1,3,4]
 *      解释：
 *          上图表示输入的链表。修改后的链表包含：
 *          - 标记为绿色的节点之和：1 = 1
 *          - 标记为红色的节点之和：3 = 3
 *          - 标记为蓝色的节点之和：2 + 2 = 4
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *     <li>列表中的节点数目在范围 [3, 2 * 10^5] 内</li>
 *     <li>0 <= Node.val <= 1000</li>
 *     <li>不 存在连续两个 Node.val == 0 的节点</li>
 *     <li>链表的 开端 和 末尾 节点都满足 Node.val == 0</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/9 11:10
 */
public class LC2181MergeNodesInBetweenZeros_M {

    static class Solution {
        /**
         * 小优化：不使用额外空间。直接在原链表中进行修改。
         * <p>直接将两个0中间的内容累加，依次赋值到原链表中，再断开。</p>
         */
        public ListNode mergeNodes(ListNode head) {
            ListNode tempNode = head;
            // currNode.next != null：用于处理最后一个0
            for (ListNode currNode = head.next; currNode.next != null; currNode = currNode.next) {
                // 未遇到0，值累加
                if (currNode.val != 0) {
                    tempNode.val += currNode.val;
                }
                // 遇到0。使用下一个节点，并将值置为0
                else {
                    tempNode = tempNode.next;
                    tempNode.val = 0;
                }
            }
            tempNode.next = null;
            return head;
        }

        public ListNode mergeNodes2(ListNode head) {
            ListNode dummyNode = new ListNode(-1);
            ListNode tempNode = dummyNode;
            int sum = 0;
            for (ListNode currNode = head.next; currNode != null; currNode = currNode.next) {
                if (currNode.val != 0) {
                    sum += currNode.val;
                } else {
                    tempNode.next = new ListNode(sum);
                    tempNode = tempNode.next;
                    sum = 0;
                }
            }
            return dummyNode.next;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(0);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(1);
        head1.next.next.next = new ListNode(0);
        head1.next.next.next.next = new ListNode(4);
        head1.next.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next.next = new ListNode(2);
        head1.next.next.next.next.next.next.next = new ListNode(0);

        Solution solution = new Solution();
        Printer.printListNode(solution.mergeNodes(head1));
    }
}